#include <iostream>
#include <vector>
#include "utils.h"
using namespace std;

class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int>::iterator beg, vector<int>::iterator end){
        if (beg == end) return NULL;
        vector<int>::iterator mid = beg + ((end-beg)>>1);
        TreeNode *root = new TreeNode(*mid);
        root->left = sortedArrayToBST(beg, mid);
        root->right = sortedArrayToBST(mid+1, end);
        return root;
    }

    TreeNode *sortedArrayToBST(vector<int> &num) {
        return sortedArrayToBST(num.begin(), num.end());
    }
};

int main(int argc, char *argv[])
{
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8};
    vector<int> v(a, a+sizeof(a)/sizeof(int));
    print_vector(v);

    Solution ss;
    TreeNode *root = ss.sortedArrayToBST(v);
    print_vector(levelOrder(root));
    return 0;
}
